package algorithm.niuke;

public class 根据中序和前序重建二叉树 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public TreeNode reConstructBinaryTree(int[] pre, int[] in, int preL, int preR, int inL, int inR) {
        if (preL < preR) {
            Integer s = 1;
            TreeNode node = new TreeNode(pre[preL]);
            int inIndex;
            for (inIndex = inL; in[inIndex] != pre[preL]; inIndex++);
            int numLeft = inIndex - inL;
            node.left = reConstructBinaryTree(pre, in, preL + 1, preL + numLeft, inL, inIndex - 1);
            node.right = reConstructBinaryTree(pre, in, preL + numLeft + 1, preR, inIndex + 1, inR);
            return node;
        } else if (preL == preR) {
            TreeNode node = new TreeNode(pre[preL]);
            return node;
        } else {
            return null;
        }
    }
}
